package com.leecode.xiehf.page_01;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * https://leetcode-cn.com/problems/generate-parentheses/
 */
public class Solution_0022 {

    public static void main(String[] args) {
        Solution_0022 solution_0022 = new Solution_0022();
        List<String> result = solution_0022.generateParenthesis(4);
        System.out.println(result);
    }

    /**
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     * 左右两边一定是左右括号,左括号任意位置都是大于等于右括号数量
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        // 左括号右括号 前提是左括号一定要大于等于右括号的输入方式
        if (n == 0) {
            return new ArrayList<>();
        }
        List<String> list = new ArrayList<>();
        getOne("", n, n, list);
        return list;
    }

    private void getOne(String str, int left, int right, List<String> list) {
        if (left == 0 && right == 0) {
            list.add(str);
            return;
        }
        if (left > right) {
            return;
        }
        if (left > 0) {
            getOne(str + "(", left - 1, right, list);
        }
        if (right > 0) {
            getOne(str + ")", left, right - 1, list);
        }
    }
}

